The concurrently filed application of Philip M. Neches describes and claims improved data processing systems and methods which in substantial measure are based upon and emanate from a novel active logic network. The active logic network is so configured and arranged that it merges a number of concurrent, competing message packets from different sources during message transfer on the network. A converging progression of pair comparisons is continued without interruption until a winning message packet is determined, and then distributed in the opposite direction to all sources. A coherent priority scheme is employed that encompasses a variety of message types such that responses, status and control messages can be intermingled in the transmissions. In consequence of these and other factors, the ratio of data message traffic to overhead traffic on the network is significantly increased over prior systems. Moreover, the system is broadly expandable without a concomitant increase in overhead systems or software. Use of these techniques greatly facilitates the ways in which multiple message sources, such as an array of data processors may work cooperatively toward a common purpose. The copending application further discloses and claims improved multiprocessor systems, including relational data base machines, arranged both as backend processors and stand alone systems.
Reference should be made to the full co-pending application for a more detailed appreciation of the different aspects and implications of the system, and for a listing and discussion of patents that typify the present state of the art. The present application is concerned with meeting more specific needs of multiprocessor systems in general, and the referenced system in particular.
These needs pertain to the ways in which the processors intercommunicate so that they perform their own tasks efficiently and coherently within the global resource context. A versatile multiprocessor must be able to distribute subtasks in a number of ways, ascertain the status of the processors performing the subtasks, merge and sort messages, correct and revise data, and ascertain when and how resources have changed (as when processors fail or come on line). Performance of such functions has heretofore entailed the use of excessive overhead software and hardware.
As one example, it is often required in a multiprocessor system, such as a data base machine, to route messages between processors so as to select an individual destination processor, or select a class of processors, or select the destination not upon a processor identification but instead upon the portion of the data base distributed to that processor, as by a hashing technique. In some known systems a prefatory communication sequence is used, in which a linkage is established between the sending processor and one or more specific receiving processors. Repeated requests and acknowledgments may be needed to establish the linkage, and deadlock conditions that may arise must be overcome by the use of further hardware and software. In other systems a supervisory control is exercised by one processor or a bus controller, to assure that the transmitting processor is ready to transmit, that the receiving processor or processors are ready to receive, that other processors are blocked out of the linkage and that no extraneous transmissions are generated. Again, the commitment to overhead and the intricacies needed to avoid deadlocks require maintenance functions that become disproportionately large as the system is expanded (e.g. to more than 16 processors).
One objective of the present invention is to make use of the various capabilities of the Neches concept without diminution of the efficiency of the system, requiring additional software, or restricting the capacity for expansion. Another objective is to provide the needed intercommunication versatility in such a way that extremely large numbers of processors (e.g. 1024) can be used in a system without imposing overhead penalties or creating deadlock or lockout possibilities.
Another example of what is required of a modern multiprocessor system relates to how the system can assuredly determine the status of the subtasks being performed by one or a number of processors. A basic requirement is that there be an ability to interrogate a given processor as to its status, without having the interrogation affect the status or creating ambiguity as to the nature of the response. The term "semaphore" has been used in the industry to characterize the function of testing and setting a status indication without interruption. The presence of a semaphore feature is desirable, but should not be incorporated at the expense of diminished performance or increased overhead load. The determination of status in turn becomes extremely important in carrying out sort/merge operations in a multiprocessor system, because the combined results of a plurality of subtasks within a major task cannot be united until the subtasks are appropriately completed. Another requirement is that the processor report its current status and that subtasks be performed only once despite repeated interruptions and changes in the multiprocessor sequence. In most present systems processor routines can be disrupted so that significant problems can arise in these respects. It can readily be appreciated that where a plurality of processors are performing related subtasks, the sequences involved in repeated interrogations and responses as to the degree of readiness of the individual processors can require significant overhead, and that the greater the number of processors the more disproportionate is the commitment to dedicated overhead.
Illustrative of the above, a typical drawback in prior art multiprocessor systems is the so-called "distributed update" problem, which is the need to update information a copy of which may be stored in each of several processing elements. This information may consist of data records or of information used to control the operation of the system such that processing can be initiated, terminated, resumed, suspended, or rolled backwards or forwards without causing any required steps to be erroneously either duplicated or omitted. Solutions of the distributed update problem in prior art systems suffer significant limitations. Some consider only two processors at a time. Still others involve protocols of intercommunication which are so complex that they have resisted all efforts to date to prove their correctness in a mathematically rigorous manner.
The complexity of these protocols results from the need to implement a "global semaphore", a control bit which has the appearance that it is tested and set in every processor as one uninterruptable operation. The control bits reside in different processors, with variable delays in communication between them, and necessarily imperfect communications channels introduce noise and also increase the tendency to errors. Those skilled in the art will therefore readily appreciate the difficulty of giving the appearance of a single, uninterrupted operation when the elements which compose the operation are diverse, interruptible, cannot be accessed at the same times, and prone to failures between access attempts.